1. Technical Field
The invention disclosed broadly relates to data processing systems and methods and more particularly relates to cryptographic systems and methods for use in data processing systems to enhance security.
2. Background Art
The following co-pending patent applications are related to this invention and are incorporated herein by reference:
B. Brachtl, et al., "Controlled Use of Cryptographic Keys Via Generating Stations Established Control Values," U.S. Pat. No. 4,850,017, issued Jul. 18, 1989, assigned to IBM Corporation and incorporated herein by reference. PA0 S. M. Matyas, et al., "Secure Management of Keys Using Control Vectors," U.S. Pat. No. 4,941,176, issued Jul. 10, 1990, assigned to IBM Corporation and incorporated herein by reference. PA0 S. M. Matyas, et al., "Data Cryptography Operations Using Control Vectors," U.S. Pat. No. 4,918,728, issued Apr. 17, 1990, assigned to IBM Corporation and incorporated herein by reference. PA0 S. M. Matyas, et al., "Personal Identification Number Processing Using Control Vectors," U.S. Pat. No. 4,924,514, issued May 8, 1990, assigned to IBM Corporation and incorporated herein by reference. PA0 S. M. Matyas, et al., "Secure Management of Keys Using Extended Control Vectors," U.S. Pat. No. 4,924,515, issued May 8, 1990, assigned to IBM Corporation and incorporated herein by reference. PA0 S. M. Matyas, et al., "Secure Management of Keys Using Control Vectors with Multi-Path Checking," Ser. No. 07/596,637, filed Oct. 12, 1990, assigned to IBM Corporation and incorporated here by reference. PA0 S. M. Matyas, et al., "Secure Cryptographic Operations Using Alternate Modes of Control Vector Enforcement," Ser. No. 07/574,012, filed Aug. 22, 1990, assigned to IBM Corporation and incorporated here by reference. PA0 S. M. Matyas, et al., "Secure Key Management Using Programmable Control Vector Checking," U.S. Pat. No. 5,007,089, issued Apr. 9, 1991, assigned to IBM Corporation and incorporated herein by reference. PA0 S. M. Matyas, et al., "Secure Key Management Using Control Vector Translation," U.S. Pat. No. 4,993,069 issued Feb. 12, 1991, assigned to IBM Corporation and incorporated herein by reference. PA0 S. M. Matyas, et al., "Data Authentication Using Modification Detection Codes Based on a Public One Way Encryption Function," U.S. Pat. No. 4,908,861, issued Mar. 13, 1990, assigned to IBM Corporation and incorporated herein by reference. PA0 D. Abraham, et al., "Smart Card Having External Programming Capability and Method of Making Same," Ser. No. 004,501, filed Jan. 19, 1987, assigned to IBM Corporation and incorporated herein by reference. PA0 S. M. Matyas, "Technique for Reducing RSA Crypto Variable Storage", U.S. Pat. No. 4,736,423, issued Apr. 5, 1988, assigned to IBM Corporation and incorporated by reference. PA0 S. M. Matyas, et al., "Method and Apparatus for Controlling the Use of a Public Key, Based on the Level of Import Integrity for the Key, " Ser. No. 07/602,989, filed Oct. 24, 1990, assigned to IBM Corporation and incorporated herein by reference. PA0 S. M. Matyas, et al., "A Hybrid Public Key Algorithm/Data Encryption Algorithm Key Distribution Method Based on Control Vectors," Ser. No. 07/748,407, filed Aug. 22, 1991, assigned to IBM Corporation and incorporated herein by reference. PA0 S. M. Matyas et al., "Generating Public and Private Key Pairs Using a Passphrase," filed on the same day as the instant application, assigned to IBM Corporation and incorporated herein by reference.
The cryptographic architecture described in the cited patents by S. M. Matyas, et al. is based on associating with a cryptographic key, a control vector which provides the authorization for the uses of the key intended by the originator of the key. The cryptographic architecture described in the cited patents by S. M. Matyas, et al. is based on the Data Encryption Algorithm (DEA), see American National Standard X3.92-1981, Data Encryption Algorithm, American Standards Institute, New York, (Dec. 31, 1981), whereas the present invention is based on both a secret key algorithm, such as the DEA, and a public key algorithm. Various key management functions, data cryptography functions, and other data processing functions are possible using control vectors, in accordance with the invention. A system administrator can exercise flexibility in the implementation of his security policy by selecting appropriate control vectors in accordance with the invention. A cryptographic facility (CF) in the cryptographic architecture is described in the above cited patents by S. M. Matyas, et al. The CF is an instruction processor for a set of cryptographic instructions, implementing methods and key generation methods. A memory in the cryptographic facility stores a set of internal cryptographic variables. Each cryptographic instruction is described in terms of a sequence of processing steps required to transform to a set of output parameters. A cryptographic facility application program (CFAP) is also described in there referenced patents and patent applications, which defines an invocation method, as a calling sequence, for each cryptographic instruction consisting of an instruction mnemonic and an address with corresponding input and output parameters.
Public key encryption algorithms are described in a paper by W. Diffie and M. E. Hellman entitled "Privacy and Authentication: An Introduction to Cryptography," Proceedings of the IEEE, Volume 67, No. 3, March 1979, pp. 397-427. Public key systems are based on dispensing with the secret key distribution channel, as long as the channel has a sufficient level of integrity. In a public key cryptographic system, two keys are used, one for enciphering and one for deciphering. Public key algorithm systems are designed so that it is easy to generate a random pair of inverse keys PU for enciphering and PR for deciphering and it is easy to operate with PU and PR, but is computationally infeasible to compute PR from PU. Each user generates a pair of inverse transforms, PU and PR. He keeps the deciphering transformation PR secret, and makes the enciphering transformation PU public by placing it in a public directory. Anyone can now encrypt messages and send them to the user, but no one else can decipher messages intended for him. It is possible, and often desirable, to encipher with PU and decipher with PR. For this reason, PU is usually called a public key and PR is usually called a private key. A corollary feature of public key cryptographic systems is the provision of a digital signature which uniquely identifies the sender of a message. If user A wishes to send a signed message M to user B, he operates on it with his private key PR to produce the signed messages. PR was used as A's deciphering key when privacy was desired, but it is now used as his "enciphering" key. When user B receives the message S, he can recover the message M by operating on the ciphertext S with A's public PU. By successfully decrypting A's message, the receiver B has conclusive proof it came from sender A. Examples of public key cryptography are provided in the following U.S. patents: U.S. Pat. No. 4,218,582 to Hellman, et al., "Public Key Cryptographic Apparatus and Method;" U.S. Pat. No. 4,200,770 to Hellman, et al., "Cryptographic Apparatus and Method;" and U.S. Pat. No. 4,405,829 to Rivest, et al., "Cryptographic Communications System and Method."
Most cryptographic systems make use of many different types of keys, so that information encrypted with a key of one type is not affected by using a key of another type. A key assigned on the basis of the information the key encrypts or the use being make of the key. For example, a data-encrypting key encrypts data. A key-encrypting key encrypts keys. A PIN-encrypting key encrypts personal identification numbers (PINs) used in electronic funds transfer and point-of-sale applications. A MAC key is used to generate and authenticate message authentication codes (MACs).
The use of encryption is based on a strategy of protecting a large amount of information (a data file or communications session) with a smaller additional amount of information (a single key). Sophisticated key hierarchies have been divised using this principle. For example, U.S. Pat. Nos. 4,850,017, 4,941,176, 4,918,728, 4,924,514, which are based on a symmetric key algorithm such as the Data Encryption Algorithm (DEA), make use of a key hierarchy wherein keys belonging to a cryptographic device are encrypted with a single master key and stored in a key data set. The master key is stored in clear form within the cryptographic hardware. The concept of using a single master key to encrypt keys stored in a key set is known as the master key concept (see C. H. Meyer and S. M. Matyas, Cryptography--A New Dimension in Computer Data Security, John Wiley & Sons, Inc., New York, 1982.). Until now, the master key concept has been applied only to cryptographic systems based on a symmetric key cryptographic algorithm. However, the present invention extends the master key concept and teaches how it may be applied to cryptographic systems based on an asymmetric key cryptographic algorithm, and more particularly how it may be applied cryptographic systems incorporating both asymmetric and symmetric key cryptographic algorithms, generally called employing (1) an asymmetric algorithm or (2) both asymmetric and symmetric algorithms, there is still a need to use many public and private keys pairs. Hence, at a minimum, the private keys must be stored in encrypted form outside the cryptographic hardware.
In order for a cryptographic system employing the master key concept to be made operable, each device must be first initialized with a master key and one or more other keys to permit the cryptographic system to communicate cryptographically with other cryptographic systems or to distribute keys to other cryptographic systems. Typically, these keys are generated and installed using manual entry techniques. In a well designed cryptographic system, all other keys are generated and handled by the cryptographic system automatically. Keys generated by the cryptographic system are stored in encrypted form in a cryptographic key data set or transmitted in encrypted form to a designated receiving device where the key is imported (i.e. re-encrypted to a form suitable for storage and use at the receiving device). Thus, an important feature of any key management scheme is the method used to encrypt keys for sage storage in a cryptographic key data set.
At the time a key is generated, the user or user application determines, from among the range of options permitted by the key management, the form of each generated key. For example, a generated key can be produced (1) in clear form, (2) in encrypted form suitable for storage in a cryptographic key data set, or (3) form suitable for distribution to a designated receiving device. Generally, cryptographic systems have different options for generating keys in these different forms. Also, at the time a key is generated, the user or user application determines, from among the range of options permitted by the key management, the type and usage of each generated key. Type and usage information are examples of a class of key-related information called control information. For example, in U.S. Pat. Nos. 4,850,017, 4,941,176, 4,918,728, 4,924,514, 4,924,515, and 5,007,089, the control information is embodied within a data variable called the control vector. The control vector concepts taught in these U.S. patents and IBM dockets is summarized in a paper by S. M. Matyas entitled "Key handling with control vectors," IBM Systems Journal, Volume 30, No. 2, 1991, pp 151-174.
In a cryptographic system employing control vectors, every key K has an associated control vector C. Thus, K and C denote a 2-tuple, where K initializes the cryptographic algorithm by selecting an enciphering transformation and C initializes the cryptographic hardware by selecting a set of cryptographic instructions, modes, and usage that K is granted. Implementation of the control vector concept requires that K and C be coupled cryptographically. Otherwise, the key-usage attributes granted to K by C could be changed by merely replacing C with another control vector. The method for accomplishing this is based on integrating C into the functions used to encrypt and decrypt keys, called control vector encryption (CVE) and control vector decryption (CVD). FIG. 1 is a block diagram illustration showing the implementation of the CVE and CVD algorithms within a cryptographic facility 30. CF 30 contains a CVE algorithm 1, a CVD algorithm 2, a master key (KM) 3, to-be-encrypted key K 4, and a recovered key K 5. The CVE algorithm 1 encrypts a clear key K 4 within CF 30 using a variant key KM+C formed as the Exclusive OR product of master key KM 3 stored within CF 30 and control vector C 6 specified as an input to CF 30 to produce an output encrypted key value of the form e*KM+C(K) 7. Note that "+" denotes the Exclusive OR operation and e* denotes encryption with a 128-bit key. The operation of encryption consists of encrypting K with the leftmost 64 bits of KM+C then decrypting the result with the rightmost 64 bits of KM+C and then encrypting that result with the leftmost 64 bits of KM+C. The CVD algorithm 2 decrypts the encrypted key e*KM+C(K) 9 specified as an input to CF 30 with the variant key KM+C formed as the Exclusive-OR produce of master key KM 3 stored within CF 30 and control vector C 8 specified as an input to CF 30 to produce an output clear key K 5. The operation of decryption consists of decrypting e*KM+C(K) with the leftmost 64 bit of KM+C them encrypting the result with the rightmost 64 bits of KM+C and then decrypting that result with the leftmost 64 bits of KM+C. The CVE algorithm is used to encrypt and protect keys stored outside the CF. The CVD algorithm is used to decrypt and recover keys to be processed within the CF.
FIG. 2 is a block diagram illustration of the control vector encryption (CVE) algorithm. Referring to FIG. 2, C is an input control vector whose length is a multiple of 64 bits; KK is a 128-bit key-encrypting key consisting of a leftmost 64-bit part KKL and a rightmost 64- bit KKR, i.e., KK=(KKL,KKR); K is a 64-bit key or the leftmost or rightmost 64-bit part of a 128-bit to be encrypted. The specification of KK is meant to be very general. For example, KK can be the master key KM, or some other key-encrypting key. The inputs are processed as follows. Control vector C is operated on by hashing algorithm ha, described below, to produce the 128-bit output hash vector H. H is Exclusive-ORed with KK to produce 128-bit output KK+H. Finally, K is encrypted with KK+H to produce output e*KK+H(K), where e* indicates encryption with 128-bit key KK+H using an encryption-decryption-encryption (e-d-e) algorithm as defined in ANSI Standard X9.17-1985 entitled "American National Standard for Financial Institution Key Management (Wholesale)", 1985, and is ISO Standard 8732 entitled "Banking--Key Management (Wholesale)", 1988.
FIG. 3 is a block diagram illustration of the control vector decryption (CVD) algorithm. Referring to FIG. 3, C is an input control vector whose length is a multiple of 64 bits; KK is a 128-bit key-encrypting key consisting of a leftmost 64-bit part KKL and a rightmost 64-bit part KKR, i.e., KK=(KKL,KKR); e*KK+H(K) is the encrypted key to be decrypted. Control vector C is operated on by hashing algorithm ha, described below, to produce the 128-bit output hash vector H. H is Exclusive-ORed with KK to produce 128-bit output KK+H. Finally, e*KK+H(K) is decrypted with KK+H using a decryption-encryption-decryption (d-e-d) algorithm to produce output K. The d-e-d algorithm is just the inverse of the e-d-e algorithm.
FIG. 4 is a block diagram illustration of hashing algorithm ha. Hashing algorithm ha operates on input control vector C (whose length is a multiple of 64 bits) to produce a 128-bit output H, where H=ha(C). If C is 64 bits, ha(C) is set equal to (C,C), where the comma denotes concatenation, and the extension field (bits 45,46) in ha(C) is set equal to B`00`. That is, ha acts like a concatenation function. If C is 128 bits, ha(C) is set equal to C, and the extension field in ha(C) is set equal to B`01`. That is, ha acts like an identity function. If C is greater than 128 bits, ha(C) is set equal to a 128-bit one way cryptographic function of C, e.g. a 128-bit modification detection code calculated by the MDC-2 algorithm in FIG. 5, and the extension field in ha(C) is set equal to B`10`. In each of the three cases, the eighth bit of each byte in ha(C) is adjusted such that each byte has even parity. This adjustment ensures that when ha(C) is exclusive-ORed with KK, the variant key KK+h(C) has the same parity as KK. The extension field in ha(C) serves to ensure, for a fixed KK, that the set of keys of the form KK+h(C) consists of three disjoint subsets S1, S2, and S3, where S1 denotes the keys resulting from all 64-bit control vectors, S2 denotes the keys resulting from all 128-bit control vectors, and S3 denotes the key resulting from all control vectors larger than 128 bits. This prevents a form of cheating wherein the CVD algorithm is tricked into decrypting an encrypted key using a false control vector. Hashing algorithm has fulfills two important objectives. First, it handles both short and long control vectors, thus ensuring that a key-management scheme based on the control vector concept is open-ended. Second, the processing overhead to handle short control vectors (64 and 128 bits) is minimized so as to have minimal impact on the key management scheme.
As an alternate embodiment, the length of the input control vector to the hashing algorithm ha can be encoded in the extension field (bits 45,46). If the input control vector is 64 bits long, the field is B`0`, if the input control vector is 128 bits long, the field is set to B`01` and if the input control vector is longer than 128 bits, the field is set to B`10`. This has the advantage of simplifying the hashing algorithm ha so that it does not need to set the extension field in the resulting output H, except if the input control vector was greater than 128 bits.
FIG. 5 is a block diagram illustration of a cryptographic function for calculating a 128-bit modification detecting code (MDC), called the MDC-2 algorithm. Referring to FIG. 5, K1=X`5252525252525252` and L1=X`2525252525252525` are two 64-bit nonsecret constant keys. They are used only to process the first 64-bit block of plaintext, Y1. Thereafter, input value K2, K3, . . . , etc. are based on output values (A1,D1), (A2,D2), . . . , etc., and input values L2, L3, . . . , etc. are based on output values (C1,B1), (C2,B2), . . . , etc. That is, the outputs of each iteration are fed back and used as the keys at the next iteration. The 32-bit swapping function merely replaces 32-bit value B with 32-bit value D and 32-bit value D with 32-bit value B.
In summary, the prior art describes a method for controlling key usage in cryptographic systems based on a symmetric key cryptographic algorithm such as the DEA. Key usage information is stored in a control vector C which is cryptographically coupled with the key K using control vector encryption and control vector decryption algorithms, CVE and CVD, respectively. The CVE and CVD algorithms can handle both short and long control vectors. The only restriction on length is that the control vector must be a multiple of 64 bits. The control vector itself consists of a group of subfields, where each subfield has it own definition and use within the key management to control the processing of the key. Encoding the control vector as a group of independent subfields has many advantages. The processing control vector checking need only concern itself with those subfields that pertain tot he requested key usage. Thus, while the control vector may have many subfields, a particular cryptographic instruction may only need to check the encoded information in a few subfields. This speeds up the control vector checking process. Another important characteristic of the control vector is that the control vector accompanies (either explicitly or implicitly) the key wherever it goes. This is because the correct non-secret control vector must be specified to recover the correct secret key value. Thus, the control vector is available and can be checked at many different places within the cryptographic system: application program, cryptographic software, and cryptographic hardware.
Within a cryptographic system, the CVE and CVD algorithms are implemented so that their operation is transparent to the system. All clear keys are encrypted with the CVE algorithm before the keys are output from the cryptographic hardware. All encrypted keys are decrypted with the CVD algorithm before they are processed within the cryptographic hardware. Even within the cryptographic hardware, these services can be provided transparently from the cryptographic instructions that process keys. By employing a single pair of control vector encryption and decryption functions, most of the complexity associated with key handling can be encoded as information fields within the control vector and within the checking processes themselves, whereas the process of encrypting and decrypting keys and linking control vector information to the key can be handled with one common method.
The present invention provides a method for incorporating control vectors into a key management scheme that uses a public key algorithm. The reader will appreciate that while the advantages of controlling key usage with the control vector are universal in nature, the methods for accomplishing this can vary depending on the attributes of the cryptographic algorithm employed. For example, consider the method of encrypting K with a variant key KK+C to produce eKK+C(K). In this case, K is encrypted using the Data Encryption Algorithm, in which case the Exclusive-OR product of KK and C is always guaranteed to produce a valid DEA key, as DEA keys, ignoring parity bits, are maximally dense in the set of all binary numbers of their magnitude. When the cryptographic algorithm is an asymmetric algorithm such as the RSA algorithm, there are two keys PU and PR. In general, if (PU,PR) is a valid key pair, then (PU+C,PR+C) is not a valid key pair for an arbitrary value C. This is because the PU and PR key values meet certain mathematical constraints and are sparse in the set of all binary numbers of their magnitude. Thus, an alternate method for coupling C to PU and PR is needed. Moreover, encrypting one key with another can sometimes be cumbersome, e.g., when an the RSA algorithm is employed it is cumbersome to encrypt a key of one modulus value with a key of another modulus value if the value of the first modulus is greater than the value of the second modulus. This cumbersome situation must be dealt with in the underlying design so that a general methodology is achieved. The present invention will show how this is accomplished. In hybrid cryptographic systems where both a symmetric and asymmetric algorithm are implemented, the public and private keys belonging to the asymmetric algorithm can be encrypted with keys belonging to the symmetric key algorithm. In that case, the method for coupling a key and control vector can be similar to that described in the prior art. However, even here there are subtle differences that affect the design choice. For example, the public and private keys belonging to the asymmetric key algorithm are typically longer than the keys belonging to the symmetric key algorithm. Also, the possibility that the public and private keys will be of different and varying lengths must be addressed. 512-bit RSA keys are not uncommon, where a DEA master key is generally 128 bits. Thus, the CVE and CVD algorithms must be adjusted to permit long asymmetric keys to be encrypted with shorter (e.g., 128-bit) symmetric keys. Another difference is that, in theory, the public keys need not be encrypted when stored in a cryptographic key data set. However, there are advantages to handling both the public and private keys similarly. As examples, the same method for coupling the control vector and the private key can be used to couple the control vector and the public key, and the same method of authenticating the key value can be used. Also, handling the public and private keys in the same way means that all keys are handled and processed just one way, which reduces the complexity of the key management design. That is, as the private key must be encrypted to ensure that its value does not become known, the public key may also be encrypted to simplify the internal key management design, as then the key (whether public or private) will always be decrypted before being processed further.
When a public key algorithm is employed, the key lengths or key sizes are not fixed by the algorithm as with the DEA. In this case, the cryptographic system will most likely have to operate with public and private keys of different lengths, varying as much as several hundred bits. Therefore, the CVE and CVD algorithms must be designed to handle public and private keys with varying lengths. It is also important that the length of the key be made transparent from the application and the cryptographic system using the key.
In cryptographic systems based on the DEA, many cryptographic instructions that handle bulk data must be streamlined so that performance is not degraded by the introduction of the control vector and the encryption and decryption algorithms (CVE and CVD). However, when a public key (PK) algorithm is employed, the individual steps of encryption and decryption are orders of magnitude slower than encryption and decryption with the DEA. Thus, the design of a key management scheme based on a PK algorithm can have different underlying objectives. For example, key processing and key handling operations that introduce unwarranted processing overhead in a DEA-based key management, may indeed be appropriate for a PK-based key management. This is because the processing overhead while large compared to one DEA encryption may be insignificant compared to one PK encryption. In the present invention, a strategy is pursued of authenticating a key dynamically within the cryptographic hardware as part of the CVD algorithm. Relatively speaking, while this introduces significant processing overhead in a DEA-based key management scheme, it adds very little processing overhead in a PK-based key management scheme. However, this ensures that valid and strong PR and PU keys are used, and that an invalid (i.e., insecure) key value is not inadvertently used.